DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2023.11

Exploration of Graphs with Excluded Minors

Authors: Júlia Baligács, Yann Disser, Irene Heinrich, and Pascal Schweitzer

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract

We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and significantly extends the graph classes that were previously known to admit a constant competitive ratio. The main ingredient of our proof is that we find a connection between the performance of the particular exploration algorithm Blocking and the existence of light spanners. Conversely, we exploit this connection to construct light spanners of bounded genus graphs. In particular, we achieve a lightness that improves on the best known upper bound for genus g ≥ 1 and recovers the known tight bound for the planar case (g = 0).

Cite as

Júlia Baligács, Yann Disser, Irene Heinrich, and Pascal Schweitzer. Exploration of Graphs with Excluded Minors. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{baligacs_et_al:LIPIcs.ESA.2023.11,
  author =	{Balig\'{a}cs, J\'{u}lia and Disser, Yann and Heinrich, Irene and Schweitzer, Pascal},
  title =	{{Exploration of Graphs with Excluded Minors}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.11},
  URN =		{urn:nbn:de:0030-drops-186644},
  doi =		{10.4230/LIPIcs.ESA.2023.11},
  annote =	{Keywords: online algorithms, competitive analysis, graph exploration, graph spanners, minor-free graphs, bounded genus graphs}
}

Search Results

Documents authored by Baligács, Júlia

Exploration of Graphs with Excluded Minors

Abstract

Cite as

Thanks for your feedback!

Could not send message